MDP có thể được giải bằng quy hoạch tuyến tính hoặc quy hoạch. Dưới đây chúng tôi xin trình bày cách tiếp cận thứ hai.

Giả sử chúng ta đã biết hàm chuyển tiếp trạng thái P {\displaystyle P}  và hàm phần thưởng  R {\displaystyle R} , và chúng ta muốn tính khả năng mà cực đại hóa phần thưởng không mong muốn dự tính.

Họ tiêu chuẩn của các thuật toán để tính nguyên tắc tối ưu này yêu cầu lưu trữ 2 dãy (array) biểu diễn bởi trạng thái: giá trị V {\displaystyle V} , chứa các giá trị thực, và nguyên tắc π {\displaystyle \pi } chứa các hành động.  Cuối cùng của thuật toán này, π {\displaystyle \pi } sẽ chứa lời giải/ đáp số và V ( s ) {\displaystyle V(s)} sẽ chứa tổng chiết khấu (discounted sum) của các phần thưởng kiếm được (trị trung bình) bằng cách theo cách giải này từ trạng thái s {\displaystyle s} .

Thuật toán này có hai loại bước sau, được lặp đi lặp lại một số lần cho tất cả các trạng thái cho đến khi không có thay đổi nào diễn ra nữa. Chúng được định nghĩa một cách đệ quy như sau:

π ( s ) := arg ⁡ max a { ∑ s ′ P a ( s , s ′ ) ( R a ( s , s ′ ) + γ V ( s ′ ) ) } {\displaystyle \pi (s):=\arg \max _{a}\left\{\sum _{s'}P_{a}(s,s')\left(R_{a}(s,s')+\gamma V(s')\right)\right\}} V ( s ) := ∑ s ′ P π ( s ) ( s , s ′ ) ( R π ( s ) ( s , s ′ ) + γ V ( s ′ ) ) {\displaystyle V(s):=\sum _{s'}P_{\pi (s)}(s,s')\left(R_{\pi (s)}(s,s')+\gamma V(s')\right)}

Bậc của chúng phụ thuộc vào biến thể của thuật toán; Ai cũng có thể thực hiện cho tất cả các trạng thái cùng một lúc hoặc từng trạng thái một, và một số trạng thái được thực hiện thường xuyên hơn các trạng thái khác. Miễn là không có trạng thái nào bị loại trừ vĩnh viễn từ một trong các bước, thuật toán sẽ cuối cùng đi đến được lời giải đúng.

Các biến thể đáng chú ý

Phép lặp giá trị

Trong phép lặp giá trị (Bellman 1957), còn được gọi là quy nạp ngược, hàm π {\displaystyle \pi } không được sử dụng, thay vào đó, giá trị của π ( s ) {\displaystyle \pi (s)} được tính toán trong V ( s ) {\displaystyle V(s)} bất kể khi nào cần thiết. Nghiên cứu của Shapley vào năm 1953 về stochastic games (trò chơi ngẫu nhiên) bao gồm một trường hợp đặc biệt, phương pháp phép lặp giá trị cho các quá trình quyết định Markov, nhưng công trình này chỉ được công nhận sau này.[1]

Thay thế tính toán của π ( s ) {\displaystyle \pi (s)} vào tính toán của V ( s ) {\displaystyle V(s)} cho ta bước kết hợp:

V i + 1 ( s ) := max a { ∑ s ′ P a ( s , s ′ ) ( R a ( s , s ′ ) + γ V i ( s ′ ) ) } , {\displaystyle V_{i+1}(s):=\max _{a}\left\{\sum _{s'}P_{a}(s,s')\left(R_{a}(s,s')+\gamma V_{i}(s')\right)\right\},}

trong đó i {\displaystyle i} là số lần lặp. Giá trị lặp bắt đầu tại i = 0 {\displaystyle i=0} và V 0 {\displaystyle V_{0}} là một giả định của hàm giá trị. Sau đó tính toán lặp đi lặp lại V i + 1 {\displaystyle V_{i+1}} cho tất cả các trạng thái s {\displaystyle s} , cho đến khi V {\displaystyle V} hội tụ với phía bên trái bằng phía bên phải (được gọi là "phương trình Bellman cho bài toán này).

Phép lặp nguyên tắc

Trong phép lặp nguyên tắc (Howard 1960) bước một được thực hiện một lần, sau đó bước 2 được lặp đi lặp lại cho đến khi nó hội tụ. Sau đó bước một được thực hiện lại một lần nữa và vv.

Thay vì lặp đi lặp lại bước hai cho đến khi hội tụ, nó có thể được xây dựng và giải như một tập hợp các phương trình tuyến tính.

Biến thể này có lợi thế là có một điều kiện dừng nhất định: khi dãy π {\displaystyle \pi } không thay đổi trong quá trình áp dụng bước 1 cho tất cả các trạng thái, thuật toán sẽ được hoàn thành.

Phép lặp nguyên tắc sửa đổi

Trong phép lặp nguyên tắc sửa đổi (van Nunen, 1976; Puterman và Shin 1978), bước một được thực hiện một lần, và sau đó bước 2 được lặp đi lặp lại nhiều lần. Sau đó bước một được thực hiện một lần nữa và vân vân.

Quét ưu tiên

Trong biến thể này, các bước được áp dụng ưu tiên cho các trạng thái quan trọng theo một số cách thức nào đó -  hoặc là dựa trên thuật toán này (có các thay đổi lớn trong V {\displaystyle V} hoặc π {\displaystyle \pi } xung quanh các trạng thái này gần đây) hoặc là dựa trên việc sử dụng (các trạng thái đó nằm gần trạng thái khởi động, hoặc là tùy thuộc vào người hoặc chương tình sử dụng thuật toán này).